package com.scc.leetcode.链表;

/**https://leetcode-cn.com/problems/reverse-linked-list/
 * 
 * 输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
 * 
 * @author yons
 *
 */
public class _206_反转链表 {
	
	
	/**迭代方法
	 * @param head
	 * @return
	 */
	public ListNode reverseList(ListNode head) {
		if(head == null || head.next == null) return head;
		
		ListNode newHead = null;
		while(head != null) {
			ListNode temp = head.next;
			head.next = newHead;
			newHead = head;
			head = temp;
		}
		
		return newHead;
    }
	
	
	/**递归方法
	 * @param head
	 * @return
	 */
	public ListNode reverseList1(ListNode head) {
		if(head == null || head.next == null) return head;
		ListNode newHead = reverseList1(head.next);
		head.next.next = head;
		head.next = null; //重要
		return newHead;
    }
	
	
	public static void main(String[] args) {
		
		ListNode note5 = new ListNode(5, null);
		ListNode note4 = new ListNode(4, note5);
		ListNode note3 = new ListNode(3, note4);
		ListNode note2 = new ListNode(2, note3);
		ListNode note1 = new ListNode(1, note2);
		
		_206_反转链表  a = new _206_反转链表();
		ListNode note =  a.reverseList1(note1);
		System.out.println(note.val);
		
	}
	
	
}
